import java.util.*;
import java.util.stream.IntStream;

/**
 * Creat with IntelliJ IDEA
 * Description:
 * User:WZW
 * Date:2022-04-05
 * Time:11:33
 */

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }

    public void show(ListNode node){
        System.out.print(node.val+" ");
        while (node.next != null){
            node = node.next;
            System.out.print(node.val+" ");
        }
        System.out.println();
    }
}

class MinStack {

    Stack<int[]> stack;
    public MinStack() {
        stack = new Stack<>();
    }

    public void push(int val) {
        if (stack.size() == 0){
            stack.push(new int[]{val,val});
        }else {
            int tmp = stack.peek()[1];
            int min = Math.min(tmp,val);
            stack.push(new int[]{val,min});
        }
    }

    public void pop() {
        stack.pop();
    }

    public int top() {
        return stack.peek()[0];
    }

    public int getMin() {
        return stack.peek()[1];
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class LRUCache {
    //这个代码写起来有很多漏洞，如果画了图会清晰很多，能考虑得更周全。
    class Node{
        int key;
        int val;
        Node prev;
        Node next;
        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    int capacity;
    int size = 0;
    Node head = new Node(0,-1);
    Node last = new Node(0, -1);
    HashMap<Integer,Node> map = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = last;
        last.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        up(node);
        return node.val;
    }

    public void up(Node cur) {
        //将Node移出
        cur.prev.next = cur.next;
        cur.next.prev = cur.prev;
        //将Node放到最前面
        head.next.prev = cur;
        cur.next = head.next;
        cur.prev = head;
        head.next = cur;
    }

    public void remove() {
        if (size == 0) return;
        Node del = last.prev;
        del.prev.next = last;
        last.prev = del.prev;
        map.remove(del.key);
        size--;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node cur = map.get(key);
            cur.val = value;
            up(cur);
            return;
        }
        if (size == capacity) {
            remove();
        }
        Node node = new Node(key, value);
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
        map.put(key, node);
        size++;
    }
}

public class Solution {

    public static void main(String[] args) {
        Solution s = new Solution();
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        ListNode n6 = new ListNode(6);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        int[] a = {3,2,1,5,6,4};
        int[] b = {2,1};
        System.out.println(s.reverseWords("god ding"));
    }

    //557. 反转字符串中的单词 III
    public String reverseWords(String s) {
        if (s == null || s.length() == 1) return s;
        String ret = "";
        int i = 0;
        while (i < s.length()) {
            int start = i;
            while (i < s.length() && s.charAt(i) != ' ') {
                i++;
            }
            for (int j = i - 1; j >= start; j--) {
                ret += s.charAt(j);
            }
            if (i < s.length() && s.charAt(i) == ' ') {
                ret += s.charAt(i);
                i++;
            }
        }
        return ret;
    }

    public String reverseWords1(String s) {
        if (s == null || s.length() == 1) return s;
        String[] ss = s.split(" ");
        s = "";
        for (int i = 0; i < ss.length; i++) {
            if (i > 0) {
                s += " ";
            }
            StringBuilder stringBuilder = new StringBuilder(ss[i]);
            stringBuilder.reverse();
            ss[i] = stringBuilder.toString();
            s += ss[i];
        }
        return s;
    }

    //292. Nim 游戏
    public boolean canWinNim(int n) {
        return n % 4 != 0;
    }

    //238.除自身以外数组的乘积
    //前后缀法
    public int[] productExceptSelf(int[] nums) {
        int[] pro = new int[nums.length];
        pro[0] = 1;
        pro[1] = nums[0];
        for (int i = 2; i < nums.length; i++) {
            pro[i] = pro[i-1] * nums[i-1];
        }
        int r = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            r *= nums[i + 1];
            pro[i] *= r;
        }
        return pro;
    }

    //217.存在重复元素
    //法二
    public boolean containsDuplicate(int[] nums) {
        return IntStream.of(nums).distinct().count() != nums.length;
    }

    public boolean containsDuplicate1(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int n : nums) {
            if (set.contains(n)){
                return true;
            } else {
                set.add(n);
            }
        }
        return false;
    }

    //215.数组中的第K个最大元素 - 大根堆
    //堆排
    public int findKthLargest(int[] nums, int k) {
        createHeap(nums);
        for (int i = 0; i < k - 1; i++) {
            swap(nums,0,nums.length - 1 - i);
            shiftDown(nums,nums.length - 1 - i,0);
        }
        return nums[0];
    }

    public void createHeap(int[] array) {
        for (int i = (array.length - 1 - 1) / 2; i >= 0; i--) {
            shiftDown(array,array.length,i);
        }
    }

    public void shiftDown(int[] array, int size, int index) {
        int left = index * 2 + 1;
        while (left < size) {
            int max = left;
            int right = left + 1;
            if (right < size && array[left] < array[right]) {
                max = right;
            }
            if (array[index] >= array[max]) {
                break;
            }
            swap(array,max,index);
            index = max;
            left = index * 2 + 1;
        }
    }

    //快排优化
    public Random random = new Random(System.currentTimeMillis());
    public int findKthLargest1(int[] nums, int k) {
        if (nums.length == 1) return nums[0];
        int left = 0;
        int right = nums.length - 1;
        int target = nums.length - k;
        int index = 0;
        while (left < right) {
            index = partition(nums,left,right);
            if (index == target) {
                return nums[index];
            } else if (index < target) {
                left = index + 1;
            } else {
                right = index - 1;
            }
        }
        return nums[left];
    }

    public int partition(int[] nums, int left, int right) {
        int r = left + 1 + random.nextInt(right - left);
        swap(nums,left,r);
        int pivot = nums[left];
        int i = left;
        int j = right;
        while (i < j) {
            while (j > i && nums[j] >= pivot) {
                j--;
            }
            nums[i] = nums[j];
            while (j > i && nums[i] <= pivot) {
                i++;
            }
            nums[j] = nums[i];
        }
        nums[i] = pivot;
        return i;
    }

    public int sort(int[] nums, int left, int right) {
        int r = random.nextInt(right - left);
        swap(nums,left,r);
        int num = nums[left];
        int d = left + 1;
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < num) {
                swap(nums,i,d);
                d++;
            }
        }
        swap(nums,d,left);
        return d;
    }

    public void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

    //237.删除链表中的节点
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

    //169.多数元素
    //投票法更漂亮的写法
    public int majorityElement(int[] nums) {
        int x = 0;
        int count = 0;
        for (int n : nums) {
            if (count == 0) {
                x = n;
            }
            count += x == n ? 1 : -1;
        }
        return x;
    }
    //投票法
    public int majorityElement2(int[] nums) {
        if (nums == null) return 0;
        int x = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == x) {
                count++;
            } else if (count > 0) {
                count--;
            } else if (count <= 0) {
                x = nums[i];
                count = 1;
            }
        }
        return x;
    }
    //排序法
    public int majorityElement1(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        Arrays.sort(nums);
        return nums[nums.length/2];
    }

    //160. 相交链表
    //法二：我走你走过的路
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return headA == null ? headB : headA;
        }
        ListNode l1 = headA, l2 = headB;
        while (l1 != l2) {
            l1 = l1 == null ? headB : l1.next;
            l2 = l2 == null ? headA : l2.next;
        }
        return l1;
    }

    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return headA == null ? headB : headA;
        }
        ListNode l1 = headA;
        ListNode l2 = headB;
        while (l1 != null && l2 != null && l1 != l2) {
            l1 = l1.next;
            l2 = l2.next;
            if (l1 == l2) break;
            if (l1 == null ) {
                l1 = headB;
            }
            if (l2 == null) {
                l2 = headA;
            }
        }
        return l1;
    }

    //法一：
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return headA == null ? headB : headA;
        }
        int c1 = 0, c2 = 0;
        ListNode cur = headA;
        while (cur != null) {
            c1++;
            cur = cur.next;
        }
        cur = headB;
        while (cur != null) {
            c2++;
            cur = cur.next;
        }
        ListNode l1 = headA;
        ListNode l2 = headB;
        if (c2 > c1) {
            int c = c2 - c1;
            while (c > 0) {
                l2 = l2.next;
                c--;
            }
        } else {
            int c = c1 - c2;
            while (c > 0) {
                l1 = l1.next;
                c--;
            }
        }
        while (l1 != null && l2 != null && l1 != l2) {
            l1 = l1.next;
            l2 = l2.next;
        }
        if (l1 == null || l2 == null) {
            return null;
        }
        return l1;
    }

    //148. 排序链表 分治递归 合并递归两个有序链表
    public ListNode sortList(ListNode head) {
        return sort(head,null);
    }

    public ListNode sort(ListNode start, ListNode end) {
        if (start == end) return start;
        ListNode fast = start;
        ListNode slow = start;
        while (fast != end && fast.next!=end) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode l2 = sort(slow.next,end);
        slow.next = null;
        ListNode l1 = sort(start,slow);
        return merge(l1,l2);
    }

    public ListNode merge(ListNode head1, ListNode head2) {
        if (head1 == null) return head2;
        if (head2 == null) return head1;
        if (head1.val <= head2.val) {
            head1.next = merge(head1.next, head2);
            return head1;
        } else {
            head2.next = merge(head1,head2.next);
            return head2;
        }
    }

    //142.环形链表II
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        if (fast == null || fast.next == null) return null;
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

    //141.环形链表
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode fast = head;
        ListNode last = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            last = last.next;
            if (fast == last) return true;
        }
        return false;
    }

    //121.买卖股票的最佳时机
    public int maxProfit1(int[] prices) {
        if (prices == null || prices.length <= 1) return 0;
        int min = prices[0];
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < min) {
                min = prices[i];
            }
            if ((prices[i] - min) > max) {
                max = prices[i] - min;
            }
        }
        return max;
    }

    //88.合并两个有序数组
    //逆向双指针
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        while (k >= 0 && j >= 0) {
            while (i >= 0 && nums1[i] >= nums2[j]) {
                nums1[k--] = nums1[i--];
            }
            nums1[k--] = nums2[j--];
        }
    }

    public void merge1(int[] nums1, int m, int[] nums2, int n) {
        for (int i = m, j = 0; j < n; j++,i++) {
            nums1[i] = nums2[j];
        }
        Arrays.sort(nums1);
    }

    //70.爬楼梯
    public int climbStairs(int n) {
        int[] a = new int[n+1];
        a[0] = 1;
        a[1] = 2;
        for (int i = 2; i < n; i++) {
            a[i] = a[i-1] + a[i-2];
        }
        return a[n-1];
    }

    //62.不同路径
    public int uniquePaths(int m, int n) {
        int[][] a = new int[m][n];
        for (int i = 0; i < m; i++) {
            a[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            a[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                a[i][j] = a[i-1][j] + a[i][j-1];
            }
        }
        return a[m-1][n-1];
    }

    //61.旋转链表
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) return head;
        ListNode cur = head;
        int count = 0;
        while (cur != null) {
            cur = cur.next;
            count++;
        }
        count = k % count;
        ListNode fast = head;
        ListNode slow = head;
        while (count > 0) {
            fast = fast.next;
            count--;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        fast.next = head;
        ListNode newHead = slow.next;
        slow.next = null;
        return newHead;
    }

    //172.阶乘后的零
    public int trailingZeroes(int n) {
        return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
    }

    //59.螺旋矩阵 II
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int i = -1;
        int j = -1;
        int count = 0;
        while (count < n * n) {
            i++;
            j++;
            while (j < n && matrix[i][j] == 0) {
                matrix[i][j++] = ++count;
            }
            j--;
            i++;
            while (i < n && matrix[i][j] == 0) {
                matrix[i++][j] = ++count;
            }
            i--;
            j--;
            while (j >= 0 && matrix[i][j] == 0) {
                matrix[i][j--] = ++count;
            }
            j++;
            i--;
            while (i >= 0 && matrix[i][j] == 0) {
                matrix[i--][j] = ++count;
            }
        }
        return matrix;
    }

    //54.螺旋矩阵
    public List<Integer> spiralOrder(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        int i = -1;
        int j = -1;
        List<Integer> list = new ArrayList<>();
        while (list.size() < row * col) {
            i++;
            j++;
            while (j < col && matrix[i][j] >= -100) {
                list.add(matrix[i][j]);
                matrix[i][j] = -101;//标记已经添加
                j++;
            }
            i++;
            j--;
            while (i < row && matrix[i][j] >= -100) {
                list.add(matrix[i][j]);
                matrix[i][j] = -101;
                i++;
            }
            i--;
            j--;
            while (j >= 0 && matrix[i][j] >= -100) {
                list.add(matrix[i][j]);
                matrix[i][j] = -101;
                j--;
            }
            j++;
            i--;
            while (i >= 0 && matrix[i][j] >= -100) {
                list.add(matrix[i][j]);
                matrix[i][j] = -101;
                i--;
            }
        }
        return list;
    }

    //334反转字符串
    public void reverseString(char[] s) {
        if (s == null || s.length == 0 || s.length == 1) return;
        int l = 0;
        int r = s.length -1;
        while (l < r) {
            char tmp = s[l];
            s[l] = s[r];
            s[r] = tmp;
            l++;
            r--;
        }
        return;
    }

    //106.反转链表
    //迭代
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode cur = head.next;
        ListNode newHead = head;
        while (cur != null) {
            head.next = cur.next;
            cur.next = newHead;
            newHead = cur;
            cur = head.next;

        }
        return newHead;
    }

    //进阶 - 尝试用递归
    public ListNode re(ListNode head) {
        if (head == null || head.next == null) {
            newHead = head;
            return head;
        }
        ListNode ret = re(head.next);
        ret.next = head;
        head.next = null;
        return head;
    }

    public ListNode newHead = null;
    public ListNode reverseList1(ListNode head) {
        re(head);
        return newHead;
    }


    //最大子数组和：简单动态规划
    //解法二：分治法 使用数据结构线段树 // 这个还是不太会

    //初始：f(i) = arr[0]
    //转移：f(i) = f(i-1) > 0 ? f(i-1) + arr[i] : arr[i] //有贪心
    public int maxSubArray(int[] nums) {
        if (nums.length == 1) return nums[0];
        int sum = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sum = sum > 0 ? sum + nums[i] : nums[i];
            max = Math.max(sum, max);
        }
        return max;
    }

    //236. 二叉树的最近公共祖先
    //解法一：用两个栈自底向上存储路径，依次pop()，最后一个相同的即为ans
    //解法二：遍历树，使用HashMap保存每个值对应的父节点
    //       并用一个HashSet保存p节点的所有祖先节点路径，
    //       取出q节点的祖先节点，HashSet中首次包含q的祖先节点时，该节点即为ans
    //解法三：判断左右子树中：（从二叉搜索树延伸过来）
    //              分别从左/右子树中找节点，找返回节点，找不到返回null
    //      两种情况：1)p&q分别在左右子树中 遍历得到左右子树均不为空，则root是ans
    //              2)p和q本身有一个是祖先 遍历得到其中一个子树为空，则不为空的节点是ans

    public HashMap<Integer,TreeNode> parent = new HashMap<>();
    public HashSet<TreeNode> ancestor = new HashSet<>();

    public void saveParent(TreeNode root) {
        if (root == null) return;
        if (root.left != null) {
            parent.put(root.left.val, root);
        }
        if (root.right != null) {
            parent.put(root.right.val, root);
        }
        saveParent(root.right);
        saveParent(root.left);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) return null;
        saveParent(root);
        while (p != null) {
            ancestor.add(p);
            p = parent.get(p.val);
        }
        while (true) {
            if (ancestor.contains(q)) return q;
            q = parent.get(q.val);
        }
    }

    //最高效
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) return null;
        if (root.val == p.val || root.val == q.val) return root;
        TreeNode leftSon = lowestCommonAncestor2(root.left, p, q);
        TreeNode rightSon = lowestCommonAncestor2(root.right,p ,q);
        if (leftSon != null && rightSon != null) return root;
        if (leftSon != null) return leftSon;
        else return rightSon;
    }

    public boolean getPath(TreeNode root, TreeNode target, Stack<TreeNode> stack){
        if (root == null) return false;
        if (root.val == target.val) {
            stack.push(root);
            return true;
        }
        if (getPath(root.left,target,stack)) {
            stack.push(root);
            return true;
        }
        if (getPath(root.right,target,stack)){
            stack.push(root);
            return true;
        }
        return false;
    }


    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) return null;
        Stack<TreeNode> stackp = new Stack<>();
        Stack<TreeNode> stackq = new Stack<>();
        TreeNode cur = root;
        if (getPath(root, p, stackp) && getPath(root, q, stackq)) {
            while (!stackp.isEmpty() && !stackq.isEmpty()) {
                TreeNode tmp = stackp.pop();
                if (tmp == stackq.pop()) cur = tmp;
                else break;
            }
        }
        return cur;
    }

    //235. 二叉搜索树的最近公共祖先
    public TreeNode lowestCommonAncestor0(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) return null;
        if (root.val == p.val || root.val == q.val) return root;
        if (p.val > q.val) return lowestCommonAncestor(root,q,p);//保证p节点的值永远是最小的那个
        if (root.val < q.val && root.val > p.val) return root;
        if (root.val > q.val) return lowestCommonAncestor(root.left,p,q);//在根节点左边
        else return lowestCommonAncestor(root.right,p,q);//在根节点右边
    }

    //230. 二叉搜索树中第K小的元素
    public int getNum(TreeNode root) {
        if (root == null) return 0;
        return getNum(root.left) + getNum(root.right) + 1;
    }

    public int kthSmallest(TreeNode root, int k) {
        if (root == null) return 0;
        if (getNum(root.left) == k - 1 ) return root.val;
        if (getNum(root.left) < k - 1) return kthSmallest(root.right, k - getNum(root.left) - 1);
        return kthSmallest(root.left, k);
    }


    //二叉树中的最大路径和
    int max = Integer.MIN_VALUE;

    public int getPath(TreeNode root){
        if (root == null) return 0;
        int l = Math.max(getPath(root.left), 0);
        int r = Math.max(getPath(root.right), 0);
        max = Math.max(max,l+r+root.val);
        return Math.max(l, r) + root.val;
    }

    public int maxPathSum(TreeNode root) {
        if (root == null) return 0;
       getPath(root);
       return max;
    }

    //二叉树的最大深度
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int l = maxDepth(root.left) + 1;
        int r = maxDepth(root.right) + 1;
        return Math.max(l,r);
    }

    //2的幂
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) return false;
        return (n & n-1) == 0;
    }

    //只出现一次的数字
    public int singleNumber(int[] nums) {
        int a = nums[0];
        for (int i = 1; i < nums.length; i++) {
            a ^= nums[i];
        }
        return a;
    }

    //买卖股票的最佳时机II
    public int maxProfit(int[] prices) {
        if (prices.length == 1) return 0;
        int i = 0;
        int j = 1;
        int profit = 0;
        while (i < prices.length && j < prices.length){
            while (i < prices.length && j < prices.length && prices[i] >= prices[j]){
                i++;
                j++;
            }//前一天票价高，此时无利润不买入
            while (i < prices.length && j < prices.length && prices[i] < prices[j]){
                profit += prices[j] - prices[i];
                i++;
                j++;
            }
        }
        return profit;
    }

    public List<Integer> grayCode(int n){
        List<Integer> list = new ArrayList<Integer>();
        if (n == 0) return list;
        list.add(0);
        list.add(1);
        int first = 2;
        for (int i = 1; i < n; i++) {
            for (int j = list.size() - 1; j >= 0; j--) {
                list.add(list.get(j)+first);
            }
            first <<= 1;
        }
        return list;
    }

    //别人的代码
    public List<Integer> grayCode2(int n) {
        List<Integer> result = new ArrayList<>();
        // 先将0加入
        result.add(0);
        if(n == 0){
            return result;
        }
        // 由于最高位前默认为 0 所以只需将当前result 按照倒叙输出并在每一个二进制前面加first即可
        int first = 1;
        for (int i = 0; i < n; i++) {
            for (int j = result.size() - 1; j >= 0; j--)
                result.add(first + result.get(j));
            // 左移一位
            first = first << 1;
        }
        return result;
    }

    public boolean countOne(int num){
        return (num & (num - 1))== 0;
    }

    public boolean gray(int num, List<Integer> path, int depth, boolean[] flg){
        if (depth == 0){
            path.add(0);
            gray(num, path, depth+1,flg);
            return true;
        }
        if (depth == num) return true;
        int i = 1;
        for (; i < num; i++) {
            if (!flg[i-1] && countOne(path.get(depth - 1)^i)){
                if (depth == num - 1 && !countOne(i ^ 0)){
                    return false;
                }
                flg[i-1] = true;
                path.add(i);
                if (!gray(num,path,depth + 1, flg)){
                    path.remove(path.size() - 1);
                    flg[i-1] = false;
                }
            }
        }
        if (path.size() == num) return true;
        return false;
    }

    //19 格雷码序列
    public List<Integer> grayCode1(int n) {
        int len = (int)Math.pow(2,n);
        boolean[] flg = new boolean[len];
        List<Integer> list = new ArrayList<>();
        gray(len,list,0,flg);
        return list;
    }

    //18 子集

    public void backtrack(int[] nums,  List<List<Integer>> list, List<Integer> path, int depth){
        if (depth >= nums.length){
            list.add(new ArrayList<>(path));
            return;
        }
        path.add(nums[depth]);
        backtrack(nums,list,path,depth+1);
        path.remove(path.size() - 1);
        backtrack(nums,list,path,depth+1);
    }

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums.length == 0) return ans;
        List<Integer> list = new ArrayList<>();
        backtrack(nums,ans,list,0);
        return ans;
    }


    //17 全排列
    public void dfs1(int[] nums, List<List<Integer>> ans,List<Integer> path, int depth,boolean[] flg){
        if (depth >= nums.length){
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!flg[i]){
                path.add(nums[i]);
                flg[i] = true;
                dfs1(nums,ans,path,depth+1,flg);
                path.remove(depth);
                flg[i] = false;
            }
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums.length == 0) return ans;
        if (nums.length == 1) {
            List<Integer> list = new ArrayList<>();
            list.add(nums[0]);
            ans.add(list);
            return ans;
        }
        List<Integer> path = new ArrayList<>();
        boolean[] flg = new boolean[nums.length];
        dfs1(nums,ans,path,0,flg);
        return ans;
    }

    //16字符串相乘
    //优化解法
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) return "0";
        int flg = 0;
        int[] ans = new int[num1.length()+num2.length()];
        for (int i = num1.length() - 1; i >= 0; i--) {
            int a = num1.charAt(i) - '0';
            for (int j = num2.length() - 1; j >= 0; j--) {
                int b = num2.charAt(j) - '0';
                int sum = a * b + ans[i + j + 1];
                ans[i + j + 1] = sum % 10;
                ans[i + j] += sum / 10;
            }
        }
        StringBuilder ret = new StringBuilder();
        for (int i = 0; i < ans.length; i++) {
            if (i == 0 && ans[i] == 0) continue;
            ret.append(ans[i]+"");
        }
        return ret.toString();
    }
    //通常解法
    public String multiply1(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) return "0";
        int flg = 0;
        String[] str = new String[num2.length()];
        for (int i = num2.length() - 1; i >= 0; i--) {
            StringBuilder ans = new StringBuilder();
            int n1 = i;
            while (num2.length() - n1 > 1) {
                ans.append("0");
                n1++;
            }
            for (int j = num1.length() - 1; j >= 0 ; j--) {
                int a = num2.charAt(i)-'0';
                int b = num1.charAt(j)-'0';
                int num = a * b + flg;
                ans.append(num % 10 + "");
                flg = num / 10;
            }
            if (flg > 0){
                ans.append(flg + "");
                flg = 0;
            }
            str[i] = ans.toString();
        }
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < str[0].length(); i++) {
            int n = flg;
            for (int j = 0; j < str.length; j++) {
                if (i < str[j].length()){
                   n += str[j].charAt(i) - '0';
                }
            }
            ans.append(n % 10 + "");
            flg = n / 10;
        }
        if (flg > 0){
            ans.append(flg + "");
        }
        ans.reverse();
        return ans.toString();
    }

    public int searchNum(int[] nums, int left, int right, int target){
        if (target == nums[left]) return left;
        if (left >= right) return -1;
        if (target == nums[right]) return right;
        int mid = (left + right) >> 1;
        if (target == nums[mid]) return mid;
        if (nums[mid] > nums[left]){//左边是有序的
            //nums[left] - nums[mid]
            if (target < nums[mid] && target > nums[left]){
                return searchNum(nums,left,mid,target);
            }else {
                return searchNum(nums,mid+1,right,target);
            }
        }else {
            //右边有序
            //nums[mid] - nums[riight]
            if (target < nums[right] && target > nums[mid]){
                return searchNum(nums,mid+1,right,target);
            }else {
                return searchNum(nums,left,mid,target);
            }
        }
    }

    //15搜索旋转排序数组
    //循环实现
    public int search(int[] nums, int target) {
        if (nums.length == 1 && nums[0] == target) return 0;
        if (nums.length <= 1) return -1;
        int l = 0, r = nums.length - 1;
        while (l <= r){
            int m = (l + r) >> 1;
            if (nums[m] == target) return m;
            if (nums[m] >= nums[l]){
                //左边有序
                if (target < nums[m] && target >= nums[l]) r = m - 1;
                else l = m + 1;
            }else {
                //右边有序
                if (target > nums[m] && target <= nums[r]) l = m + 1;
                else r = m - 1;
            }
        }
        return -1;
    }
    //递归实现
    public int search1(int[] nums, int target) {
        if (nums.length == 1 && nums[0] == target) return 0;
        if (nums.length <= 1) return -1;
        return searchNum(nums,0,nums.length - 1,target);
    }



    //14 删除有序数组中的重复项
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return 1;
        int count = 1;
        int index = 0;
        int i = 1;
        while (i < nums.length){
            if (nums[i-1] == nums[i]){

                while (i < nums.length && nums[i-1] == nums[i]){
                    i++;
                }
            }
            if (i >= nums.length) return index+1;
            nums[index+1] = nums[i];
            index++;
            i++;
        }
        return index+1;
    }

    //13 合并K个升序链表

    //*循环*代替递归的分治法
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        for (int i = 1; i < lists.length; i *= 2) {//步长 两两合并的单个链表的步长
            for (int j = i; j < lists.length; j += i*2) {//往前i步的合并，下一次到两倍步长
                lists[j-i] = mergeTwoLists(lists[j-i],lists[j]);
//                lists[j] = null;//不需要
            }
        }
        return lists[0];
    }

    public ListNode merge(ListNode[] lists, int start, int end){
        if (start == end) return lists[start];
        if (start > end) return null;
        int mid = (start + end) >> 1;
        return mergeTwoLists(merge(lists,start,mid),merge(lists, mid + 1, end));
    }

    //解法二 分治法
    public ListNode mergeKLists2(ListNode[] lists) {
       return merge(lists,0,lists.length-1);
    }

    //解法一
    public ListNode mergeKLists1(ListNode[] lists) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        for (ListNode l : lists) {
            if (l != null) queue.offer(l);
        }
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while (!queue.isEmpty()){
            ListNode tmp = queue.poll();
            cur.next = tmp;
            cur = cur.next;
            if (tmp.next != null) queue.offer(tmp.next);
        }
        return head.next;
    }

    //12 合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while (list1 != null && list2 != null){
            while (list1 != null && list2 != null && list1.val < list2.val){
                cur.next = list1;
                cur = cur.next;
                list1 = list1.next;
            }
            while (list2 != null && list1 != null && list2.val <= list1.val){
                cur.next = list2;
                cur = cur.next;
                list2 = list2.next;
            }
        }
        if (list1 != null){
            cur.next = list1;
        }else if (list2 != null){
            cur.next = list2;
        }
        return head.next;
    }

    //11 有效的括号
    public boolean isValid(String s) {
        if (s.length() % 2 == 1) return false;//这一步没想到！！！
        Stack<Character> stack = new Stack<>();
        Stack<Character> tmp = new Stack<>();
        for (char c:s.toCharArray()) {
            stack.push(c);
        }
        while (!stack.isEmpty()){
            char cur = stack.pop();
            while (cur == ')' || cur == '}' || cur ==']'){
                tmp.push(cur);
                if (!stack.isEmpty()){
                    cur = stack.pop();
                }else {
                    break;
                }
            }
//            if (cur == ')' || cur == '}' || cur ==']') return false;
            //cur 左括号
            if (tmp.isEmpty()) return false;
            char right = tmp.pop();
            if (Math.abs(right - cur) > 2) return false;//括号不匹配
        }
        return tmp.isEmpty();
    }

    //10 最接近的三数之和
    //优化
    public int threeSumClosest(int[] nums, int target) {
        int sum = nums[0]+nums[1]+nums[2];
        if (nums.length == 3) return sum;
        Arrays.sort(nums);
        if (nums[0] == nums[nums.length-1]) return sum;
        int cloest = Integer.MAX_VALUE;
        int cloestSum = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i-1]){//去重
                continue;
            }
            for (int j = i+1; j <nums.length -1 ; j++) {
                if (j > i + 1 && nums[j] == nums[j-1]){//去重
                    continue;
                }
                int k = nums.length-1;
                sum = nums[i] + nums[j] + nums[k];
                while (k-1 > j && sum > target){
                    if (sum - target < cloest){
                        cloest = sum - target;
                        cloestSum = sum;
                    }
                    k--;
                    while (k-1 > j && nums[k]==nums[k+1]){
                        k--;
                    }
                    sum = nums[i] + nums[j] + nums[k];
                }
                if (sum <= target){
                    if (target - sum < cloest){
                        cloest = target - sum;
                        cloestSum = sum;
                        if (cloest == 0) return cloestSum;
                    }
                }else {
                    if (sum - target < cloest){
                        cloest = sum - target;
                        cloestSum = sum;
                    }
                }
            }
        }
        return cloestSum;
    }

    public int threeSumClosest1(int[] nums, int target) {
        int sum = nums[0]+nums[1]+nums[2];
        if (nums.length == 3) return sum;
        Arrays.sort(nums);
        int cloest = Integer.MAX_VALUE;
        int cloestSum = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i+1; j <nums.length -1 ; j++) {
                int k = nums.length-1;
                sum = nums[i] + nums[j] + nums[k];
                while (k-1 > j && sum > target){
                    if (sum - target < cloest){
                        cloest = sum - target;
                        cloestSum = sum;
                    }
                    k--;
                    sum = nums[i] + nums[j] + nums[k];
                }
                if (sum <= target){
                    if (target - sum < cloest){
                        cloest = target - sum;
                        cloestSum = sum;
                        if (cloest == 0) return cloestSum;
                    }
                }else {
                    if (sum - target < cloest){
                        cloest = sum - target;
                        cloestSum = sum;
                    }
                }
            }
        }
        return cloestSum;
    }

    //9 三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) return ans;
        Arrays.sort(nums);
        //先固定第一个数，把三个数的问题转化成两个数的
        //并且保证保存的三个数按顺序排列
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i-1]){//去重
                continue;
            }
            //相当于双指针
            for (int j = i+1; j < nums.length - 1 ; j++) {
                if (j > i+1 && nums[j] == nums[j-1]){//去重
                    continue;
                }
                int last = nums.length - 1;
                while (j < last && nums[j] + nums[i] + nums[last] > 0){
                    last--;
                }
                if ( j == last || nums[j] + nums[i] + nums[last] < 0){
                    continue;
                }else if (j < last && nums[j] + nums[i] + nums[last] == 0){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[last]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }

    //8
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 1) return strs[0];
        int length = strs[0].length();
        for (int i = 1; i < strs.length; i++) {
            if (strs[i].length() < length){
                length = strs[i].length();
            }
        }
        int i = 0;
        for (; i < length; i++) {
            int j = 1;
            for (; j < strs.length; j++) {
                if (strs[0].charAt(i) != strs[j].charAt(i)){
                    break;
                }
            }
            if (j < strs.length) break;
        }
        return strs[0].substring(0,i);
    }

    //7
    public int maxArea(int[] height) {
        if (height.length == 0) return 0;
        if (height.length == 1) return height[0];
        int left = 0;
        int right = height.length-1;
        int maxArea = Math.min(height[left],height[right])*(right-left);
        while (left < right){
            if (height[left]<height[right]){
                left++;
            }else {
                right--;
            }
            int newArea = Math.min(height[left],height[right])*(right-left);
            if (newArea > maxArea) maxArea = newArea;
        }
        return maxArea;
    }

    //6
    public boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;//负数一定不是回文数，直接返回
        int num = 0;
        while ( num < x){
            num = (num * 10) + (x % 10);//拼接反转的数
            x /= 10;
        }
        return x == num || x == num / 10;
    }

    //解法二
    public boolean isPalindrome2(int x) {
        if (x < 0) return false;//负数一定不是回文数，直接返回
        //找最高位
        int high = 1;
        while (x / high > 9){
            high *= 10;
        }
        //分别去首位和末尾进行判断
        while (x > 0){
            int h = x / high;
            int l = x % 10;
            if (h != l) return false;
            x %= high;//去掉最高位
            x /= 10;//去掉最低位
            high /= 100;//去掉两位后，新的最高位降低两位
        }
        return true;
    }

    //解法一
    public boolean isPalindrome1(int x) {
        if (x < 0) return false;
        String s = String.valueOf(x);
        int left = 0;
        int right = s.length() - 1;
        while (left < right){
            if (s.charAt(left) == s.charAt(right)){
                left++;
                right--;
            }else {
                return false;
            }
        }
        return true;
    }

    //5
    // 方法二 状态机


    // 方法一  要注意的点
    public int myAtoi(String s) {
        boolean flg = false;
        int num = 0;
        int i = 0 ;
        while (i<s.length() && s.charAt(i)==' ') i++;
        if (i<s.length() && (s.charAt(i)=='-'||s.charAt(i)=='+')) {
            if (s.charAt(i)=='-') flg = true;
            i++;
        }
        while (i<s.length() && Character.isDigit(s.charAt(i))){
            if (num>Integer.MAX_VALUE/10 || (num==Integer.MAX_VALUE/10 && (s.charAt(i)-'0')>7)){
                return flg?Integer.MIN_VALUE:Integer.MAX_VALUE;
            }
            num = num*10 + (s.charAt(i)-'0');
            i++;
        }
        return flg?-num:num;
    }

    //这个没过……
//    public int myAtoi(String s) {
//        boolean b = false;
//        int flg = 0;
//        int num = 0;
//        for (char c:s.toCharArray()) {
//            if (c>='0' && c<='9'){
//                b = true;
//                if (num==0) num += c-'0';
//                else {
//                    if (num >= Integer.MAX_VALUE/10 ){
//                        if (flg != -1) {
//                            if (c-'0'>= 7 || num >=) return Integer.MAX_VALUE;//2147483647
//                            num = num *10 + (c-'0');
//                        }
//                        else if (c-'0'>= 8)return Integer.MIN_VALUE;//-2147483648
//                        else num = num *10 + (c-'0');
//                    }
//                    else {
//                        num *= 10;
//                        num += c - '0';
//                    }
//                }
//            }else if (!b && (c==' ' || c=='+' || c=='-')){
//                if (c=='+') {
//                    if (flg == -1) return 0;
//                    flg = 1;
//                }
//                else if (c=='-')  {
//                    if (flg == 1) return 0;
//                    flg = -1;
//                }
//            }else break;
//        }
//        if (flg == -1) return  -num;
//        return num;
//    }

    //4
    public int reverse(int x) {
        int ret = 0;
        boolean flg = false;
        if (x < 0) {
            flg = true;
            x = -x;
        }
        while (x>0){
            if (ret > 0){
                if (ret*10/10!=ret){
                    return 0;
                }
                ret *= 10;
            }
            int i = x%10;
            x/=10;
           if (ret+i-i!=ret){
               return 0;
           }
            ret += i;
        }
        if (flg){
            ret = -ret;
        }
        return ret;
    }

    //3
    public void findLongest(String s,int left, int[] pos){
        int right = left;
        while (right<s.length()-1 && s.charAt(right)==s.charAt(right+1)) right++;
        while (left>0 && right<s.length()-1 && s.charAt(left-1)==s.charAt(right+1)){
            left--;
            right++;
        }
        if (right-left > pos[1]-pos[0]){
            pos[0] = left;
            pos[1] = right;
        }
    }

    public String longestPalindrome(String s) {
        if (s == null || s.length()==0) return "";
        int[] pos = new int[2];
        for (int i = 0; i < s.length(); i++) {
            findLongest(s,i,pos);
        }
        return s.substring(pos[0],pos[1]+1);
    }

    //2

    public double findMedianSortedArrays1_1(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if (m==0){
            if (n%2==1) return nums2[n/2];
            return (nums2[n/2-1]+nums2[n/2])/2.0;
        }
        if (n==0){
            if (m%2==1) return nums1[m/2];
            return (nums1[m/2-1]+nums1[m/2])/2.0;
        }
        int index1 = 0;
        int index2 = 0;
        int last = 0;//如果数组总长度为偶数，则还需要记录上一步的数值
        int cur = 0;//记录当前位置的数值
        for (int i = 0; i <= (m+n)/2 ; i++) {//走m+n/2步
            last = cur;
            if (index1<m && index2<n){
                if (nums1[index1] < nums2[index2]) cur = nums1[index1++];
                else cur = nums2[index2++];
            }else if (index1 < m) cur = nums1[index1++];
            else cur = nums2[index2++];
        }
        //分奇偶情况讨论
        if ((m+n)%2==1) return cur;
        return (last+cur)/2.0;
    }

    public double findMedianSortedArrays1_2(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if (m==0){
            if (n%2==1) return nums2[n/2];
            return (nums2[n/2-1]+nums2[n/2])/2.0;
        }
        if (n==0){
            if (m%2==1) return nums1[m/2];
            return (nums1[m/2-1]+nums1[m/2])/2.0;
        }
        int[] array = new int[m+n];
        int i = 0;
        int j = 0;
        //归并排序
        for (int k = 0; k < m+n; k++) {
            if (i < m && j < n ){
                if (nums1[i] < nums2[j])array[k] = nums1[i++];
                else array[k] = nums2[j++];
            }else if (i < m) array[k] = nums1[i++];
            else array[k] = nums2[j++];
        }
        //返回中位数
        if ((m+n)%2==1) return array[(m+n)/2];
        return (array[(m+n)/2-1]+array[(m+n)/2])/2.0;
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if ( m > n ) return findMedianSortedArrays(nums2,nums1);//保证数组1长度小于数组2
        if (m+n==1)return nums2[0];//提示中m+n的范围是1到2000，总长度为1时，由于数组1长度小于数组2，所以唯一的数在数组2中，直接返回
        int i = m/2;
        int j = (m+n+1)/2-i;
        while (true){//通过循环调整i和j分割的位置
            if (i>0 && j<n && nums1[i-1]>nums2[j]){//处理第一种情况
                i--;
            }else if (i<m && j>0 &&nums2[j-1]>nums1[i]){//处理第二种情况
                i++;
            }
            else{//左边都小于右边，符合条件
                int left = 0;
                int right = 0;
                //先处理左边的情况 先处理边界情况
                if (i==0)left = nums2[j-1];
                else if (j==0)left = nums1[i-1];
                else left = Math.max(nums1[i-1],nums2[j-1]);
                //如果长度为奇数则直接返回左边的最大值
                if ((n+m)%2==1) return left;
                //否则继续处理右边的情况
                if (i==m) right = nums2[j];
                else if (j==n) right = nums1[i];
                else right = Math.min(nums1[i],nums2[j]);
                return (left+right)/2.0;
            }
            j = (m+n+1)/2-i;//调节j的位置
        }
    }


    /**
     * 在给定的数组中查找第K个数
     * @param nums1 第一个数组
     * @param i 第一个数组的起始位置
     * @param nums2 第二个数组
     * @param j 第二个数组的起始位置
     * @param k 查找的第K个数
     * @return
     */
    public int findkth(int[] nums1, int i ,int[] nums2, int j ,int k){
        if (i>=nums1.length) return nums2[j+k-1];//注意落到下标上是：数组起始位置+k-1
        if (j>=nums2.length) return nums1[i+k-1];
        if (k==1) return Math.min(nums1[i],nums2[j]);
        int tmp1 = i+k/2-1<nums1.length?nums1[i+k/2-1]:Integer.MAX_VALUE;//i或j超出范围则直接赋为最大值，方便后续比较
        int tmp2 = j+k/2-1<nums2.length?nums2[j+k/2-1]:Integer.MAX_VALUE;
        return tmp1<tmp2 ? findkth(nums1,i+k/2,nums2,j,k-k/2):findkth(nums1,i,nums2,j+k/2,k-k/2);
    }

    //1,3 2
    public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int left = (m+n+1)>>1;
        int right = (m+n+2)>>1;
        return (findkth(nums1,0,nums2,0,left)+findkth(nums1,0,nums2,0,right))/2.0;//注意返回d类型为double，所以要除以2.0
    }

    //1
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int c = 0;
        int s = l1.val + l2.val;
        if (s + c > 9){
            c = 1;
            s -= 10;
        }
        ListNode head = new ListNode(s);
        ListNode sum = head;
        while (l1.next!=null && l2.next!=null){
            sum.next = new ListNode(c);
            s = l1.next.val + l2.next.val;
            if (s + c > 9){
                c = 1;
                s -= 10;
            }else {
                c = 0;
            }
            sum.next.val += s;
            l1 = l1.next;
            l2 = l2.next;
            sum = sum.next;
        }
        while (l1.next != null){
            s = l1.next.val + c;
            if (s > 9){
                c = 1;
                s -= 10;
            }else {
                c = 0;
            }
            sum.next = new ListNode(s);
            l1 = l1.next;
            sum = sum.next;
        }
        while (l2.next != null){
            s = l2.next.val + c;
            if (s > 9){
                c = 1;
                s -= 10;
            }else {
                c = 0;
            }
            sum.next = new ListNode(s);
            l2 = l2.next;
            sum = sum.next;
        }
        if (c == 1){
            sum.next = new ListNode(c);
        }
        return head;
    }
}
